package algorithmTopics.matrix;

import java.util.*;

/**
 * 矩阵相关题目的类
 *
 * @author 86155
 * @date 2025/05/18
 */
public class Solution {

    /**
     * 搜索矩阵 中找值
     *
     * @param matrix 矩阵
     * @param target 目标
     * @return boolean
     */
    public boolean searchMatrix(int[][] matrix, int target) {

        // 旋转45° 变成了二叉搜索树的版本
        for(int m = matrix.length - 1, n = 0; m >=0 && n < matrix[0].length;){
            if(target > matrix[m][n]){
                n++;
                continue;
            }else if(target < matrix[m][n]){
                m--;
                continue;
            }else{
                return true;
            }
        }
        return false;

    }

    /**
     * 旋转 数组
     *
     * @param matrix 矩阵
     */
    public void rotate(int[][] matrix) {
        int len = matrix.length;
        for (int i = 0; i < (len - 1) / 2; i++) {
            for (int j = i; j < len - i - 1; j++) {
                // 从左上角开始
                // 四个角进行旋转,按照顺时针交换位置
                int temp = matrix[i][j];
                // 看是否切换到顺时针的列上
                // 左上角 = 左下角
                matrix[i][j] = matrix[len - j - 1][i];
                // 左下角 = 右下角
                matrix[len - j - 1][i] = matrix[len - i - 1][len - j - 1];
                // 右下角 = 右上角
                matrix[len - i - 1][len - j - 1] = matrix[j][len - i - 1];
                matrix[j][len - i - 1] = temp;

            }

        }
    }

    private int[][] towards = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    /**
     * 螺旋顺序 返回一个数组
     *
     * @param matrix 矩阵
     * @return {@link List}<{@link Integer}>
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> ans = new ArrayList<>(m * n);
        int count = 1;
        for (int i = 0, j = 0; i < m && j < n; ) {
            // 添加进集合
            ans.add(matrix[i][j]);
            matrix[i][j] = 101;
            //找到属于自己的那个方向
            int[] toward = towards[count % 4];
            if (i + toward[0] >= 0 && i + toward[0] < m && j + toward[1] >= 0 && j + toward[1] < n &&
                    matrix[i + toward[0]][j + toward[1]] != 101) {
                // 在集合内
            } else {
                // 直接切换方向
                count++;
                toward = towards[count % 4];
            }
            i += toward[0];
            j += toward[1];
            if (ans.size() == m * n) {
                break;
            }


        }

        return ans;
    }

    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        Set<Integer> row = new HashSet<>();
        Set<Integer> col = new HashSet<>();
        // find zero row and column
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row.add(i);
                    col.add(j);
                }
            }
        }
        row.forEach(integer -> Arrays.fill(matrix[integer], 0));
        for (int i = 0; i < m; i++) {
            for (Integer j : col) {
                matrix[i][j] = 0;
            }
        }


    }

/*    给你两个整数 m 和 n 。构造一个 m x n 的网格，其中每个单元格最开始是白色。请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。

    涂色方案需要满足：不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。因为答案可能非常大， 返回 对 109 + 7 取余 的结果。
    1 <= m <= 5
    1 <= n <= 1000
    示例 1：
    输入：m = 1, n = 1
    输出：3*/

    private static int mod = (int) 1e9 + 7;

    public int colorTheGrid(int m, int n) {
        int res = 0;
        //状态：dp[i][mask] 表示前 i 行已经合法涂色，且第 i 行的颜色模式为 mask 时的涂色方法数。
        //如1*3的矩阵，mask=RGB,涂色的颜色从左到右依次红绿蓝 ,
        //生成所有可能的行模式
        //mask 的取值范围：对于 n 列的网格，mask 是一个 n 位的三进制数，范围是 0 到 3^n - 1。
        //初始化第一行 ,生成所有的可能
        List<Integer> integers = generateValidMasks(n);

        int maskCount = integers.size();
        // conflict[i][j] = true 表示 下标 i和 j 可以相邻（不冲突）
        boolean[][] conflict = new boolean[maskCount][maskCount];
        for (int i = 0; i < maskCount; i++) {
            for (int j = 0; j < maskCount; j++) {
                conflict[i][j] = hasConflict(integers.get(i), integers.get(j), n);
            }
        }

        int[] dp = new int[maskCount];
        //初始化结果为1
        Arrays.fill(dp, 1);

        //动态生成所有层的结果，都存储在新的list中
        for (int i = 1; i < m; i++) {
            //新的一层对于每一个mask的数量
            int[] newDp = new int[maskCount];
            for (int j = 0; j < maskCount; j++) {
                // 把每一种情况都单独对比
                for (int k = 0; k < maskCount; k++) {
                    if (conflict[k][j]) {
                        newDp[j] = dp[k] + newDp[j];
                    }
                }
            }
            dp = newDp;
        }

        //结果最后一层的方案之和
        for (int i = 0; i < maskCount; i++) {
            int stringsNum = dp[i];
            res = (res + stringsNum) % mod;
        }
        return res;
    }

    /**
     * 检查两个 mask 是否有相同列的颜色
     *
     * @param mask1 第一个三进制数（表示一行的颜色模式）
     * @param mask2 第二个三进制数
     * @param n     列数
     * @return false 如果冲突（至少一列颜色相同）
     */
    private static boolean hasConflict(int mask1, int mask2, int n) {
        for (int i = 0; i < n; i++) {
            int color1 = (mask1 / (int) Math.pow(3, i)) % 3;
            int color2 = (mask2 / (int) Math.pow(3, i)) % 3;
            if (color1 == color2) {
                return false;
            }
        }
        return true;
    }

    // 生成所有合法的三进制 mask（相邻位不同）

    private static List<Integer> generateValidMasks(int n) {
        List<Integer> validMasks = new ArrayList<>();
        int maxMask = (int) Math.pow(3, n);
        for (int mask = 0; mask < maxMask; mask++) {
            if (isValidMask(mask, n)) {
                validMasks.add(mask);
            }
        }
        return validMasks;
    }

    // 检查三进制数的相邻位是否不同
    private static boolean isValidMask(int mask, int n) {
        int prev = -1;
        for (int i = 0; i < n; i++) {
            int current = (mask / (int) Math.pow(3, i)) % 3;
            if (current == prev) {
                return false;
            }
            prev = current;
        }
        return true;
    }

    /**
     * 是否有一个词相同 : 扫描通过为ture
     *
     * @return boolean
     */
    private boolean isOneWordSame(String a, String b) {
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) == b.charAt(i)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 生成一层内的所有方案 :颜色组合枚举
     * 弊端：所占内存空间过大
     *
     * @param n n 列数量
     * @return {@link List}<{@link String}>
     */
    public List<String> generateAllMask(int n) {
        //mask 是一个 n 位的三进制数，范围是 0 到 3^n - 1。
        ArrayList<String> list = new ArrayList<>(n);
        backtrack(n, new StringBuilder(), list, '\0');
        return list;
    }

    private static final char[] COLORS = {'R', 'G', 'B'};

    private static void backtrack(int n, StringBuilder path, List<String> list, char prevColor) {
        // 当到达长度的时候 生成一个
        if (path.length() == n) {
            list.add(path.toString());
            return;
        }
        //遍历生成
        for (char c : COLORS) {
            //确保当前颜色不等于上一个
            if (c != prevColor) {
                path.append(c);
                backtrack(n, path, list, c);
                path.deleteCharAt(path.length() - 1);
            }
        }

    }


}
